package lib

//link to 292 464
func init() {
	Probs = append(Probs, Problem{
		Num:         294,
		Discription: "+-翻转游戏",
		Level:       2,
		Labels: map[string]int{
			"记忆化搜索": 1,
			"二进制状态表示":   1,
		},
	})
}

//为什么不用string表示状态：不方便修改
func CanWin(currentState string) bool {
    //已经搜索过的状态
	stateMap := make(map[int]bool, 0)
	var dfs func(int) bool
	dfs = func(state int) bool {
		if res, exist := stateMap[state]; exist {
			return res
		}

		for i := 1; i < len(currentState); i++ {
			if state&(1<<i) == 0 && state&(1<<(i-1)) == 0 {
				if !dfs(state | (1 << i) | (1 << (i - 1))) {
                    //返回的状态是，对方在下一状态下作为先手是否能赢，所以要取反
					stateMap[state] = true
					return true
				}
			}
		}

		stateMap[state] = false
		return false
	}

    //用二进制表示每一位是+还是-
	state := 0
	for i := len(currentState) - 1; i >= 0; i-- {
		if currentState[i] == '-' {
			state |= 1 << i
		}
	}

	return dfs(state)
}